#include "p2.h"

string file;
ofstream output;
bool tiempo = false;

string get_file_contents(const char *filename){
	ifstream in(filename, std::ios::in | std::ios::binary);
	if (in){
		string contents;
		in.seekg(0, std::ios::end);
		contents.resize(in.tellg());
		in.seekg(0, std::ios::beg);
		in.read(&contents[0], contents.size());
		in.close();
		return(contents);
	}
	perror("Error:");
	return 0;
}

int main(int argc, char *argv[]) {

	if(argc ==1){
		cout << "Usando p2.in y p2.out" << endl;
		file = get_file_contents("p2.in");
		output.open("p2.out");
		if(output.fail()){
			cerr << "Error al abrir archivo de salida" << endl;
		}
	}

	else if(argc ==3){
		cout << "Usando " << argv[1] << " y " << argv[2] << endl;
		file = get_file_contents(argv[1]);
		output.open(argv[2]);
		if(output.fail()){
			cerr << "Error al abrir archivo de salida" << endl;
		}
	}

	else if(argc ==2 && string (argv[1]) == "time"){
		cout << "Calculando tiempos usando p2.in y p2.out con " << ITER << " iteraciones" << endl;
		tiempo = true;
		file = get_file_contents("p2.in");
		output.open("p2.out");
		if(output.fail()){
			cerr << "Error al abrir archivo de salida" << endl;
		}
	}

	else{
		cout << "Modo de uso: \"p2 input output\" o \"p2 time\" para benchmark" << endl;
		return 0;
    }

	istringstream input;
	input.str(file);

	while(!input.eof()){
		if(input.peek() == '#'){
			break;
		}
		int n;
		int sensor;
		input >> n;
		input >> sensor;
		vector<int> inter = cargar(input,n);
		if(tiempo){
			uint64_t t;
			uint64_t res = 0;
			for(int i=0;i<ITER;i++){
				t=rdtsc();
				resolverBBin(n,sensor,inter);
				t = rdtsc() -t;
				res = res + t;
			}
		res = res/ITER;
		cout << "For n= " << n << " process took: "<< res << " ticks" << endl;
		}
		int sol = resolverBBin(n,sensor,inter);
		salida(output,sol);
	}
	output.close();
	return 0;
}

vector<int> cargar(istringstream& is, int n){
	string l;
	getline(is,l);
	istringstream ssl(l);
	vector<int> inter(n);
	for(int i=0; i < n; i++){
		ssl >> inter[i];
	}
	
	#ifdef custom_dbg
	cout << "Sensores Cargados: ";
	
	for (int i = 0; i < inter.size(); i ++)
		cout << inter[i] << ", ";
		
	cout << endl;
	#endif
	
	return inter;
}

int resolverGoloso(const int n, const int sensor, const vector<int>& inter){
	int k = sensor;
	if(k<=n){
		return k;
	}
	k= k-n;
	int min = 1;
	int veces = 0;
	while(true){
		for(int i=0;i<n;i++){
			if(min % inter[i] == 0){
				veces++;
			}
			if(k == veces){
				return i+1;
			}
		}
		min++;
	}
}

bool LeyoEnIntervalo(int frecuenciaMedicion, int tMin, int tMax)
{
	bool result = (tMax / frecuenciaMedicion) * frecuenciaMedicion >= tMin;

	#ifdef custom_dbg
	cout << "tMin: " << tMin << endl;
	cout << "tMax: " << tMax << endl;
	cout << "El sensor de frecuencia " << frecuenciaMedicion << " leyo? " << result << endl;
	#endif

	return result;
}

int LecturasHasta(int tiempo, const vector<int> intervalos)
{
	int result = intervalos.size();

	for (int i = 0; i < intervalos.size(); i++)
		result += (tiempo / intervalos[i]);
		
	return result;
}

int minFrecuencia;
int cotaSupIntervalo;
int cotaInfIntervalo;
vector<int> frecuenciasAux;

bool LeyoAntes(const int sensor1, const int sensor2)
{

	int frecuencia1 = frecuenciasAux[sensor1];
	int frecuencia2 = frecuenciasAux[sensor2];
	
	int tiempoDeLectura1 = ((cotaSupIntervalo - 1) / frecuencia1) * frecuencia1;
	int tiempoDeLectura2 = ((cotaSupIntervalo - 1) / frecuencia2) * frecuencia2;

	#ifdef custom_dbg
	cout << "Comparando: " << sensor1 << " con " << sensor2 << endl;
	cout << "Tiempo 1: " << tiempoDeLectura1 << endl;
	cout << "Tiempo 2: " << tiempoDeLectura2 << endl;
	#endif

	if (tiempoDeLectura1 == tiempoDeLectura2)
		return sensor1 < sensor2;
	
	return tiempoDeLectura1 < tiempoDeLectura2;
}

int resolverBBin(const int n, const int lecturaErronea, const vector<int>& frecuencias){

	int k = lecturaErronea;
	
	frecuenciasAux = frecuencias;
	
	if(k <= n)
		return k;
	
    //Busco m_i = min(m_j) con 1<=j<=n
    minFrecuencia = frecuencias[0];
    for (int i = 1; i < n; i++)
        if (minFrecuencia > frecuencias[i])
            minFrecuencia = frecuencias[i];

	#ifdef custom_dbg
	cout << "Minima frecuencia: " << minFrecuencia << endl;
	#endif

    //Hago la busqueda binaria
	int cotaSup = k;
    int cotaInf = 0;
    int lecturaCandidato = (cotaSup + cotaInf) / 2;
    int lecturasAnterioresACandidato;
    int lecturasHastaCandidato;
    
	int tiempoLecturaCandidato = (lecturaCandidato * minFrecuencia);

	lecturasAnterioresACandidato = 
		LecturasHasta(tiempoLecturaCandidato - minFrecuencia, frecuencias);
	lecturasHastaCandidato = 
		LecturasHasta(tiempoLecturaCandidato, frecuencias);

	#ifdef custom_dbg		
	cout << "Analizando lectura número: " << lecturaCandidato << endl;
	cout << "Lecturas hasta candidato: " << lecturasHastaCandidato << endl;
	cout << "Lecturas anteriores candidato: " << lecturasAnterioresACandidato << endl;
	#endif

	while (!(lecturasAnterioresACandidato <= k && k < lecturasHastaCandidato))
	{
		#ifdef custom_dbg
		cout << "Analizando lectura número: " << lecturaCandidato << endl;
		cout << "Lecturas hasta candidato: " << lecturasHastaCandidato << endl;
		cout << "Lecturas anteriores candidato: " << lecturasAnterioresACandidato << endl;
		#endif
		
		if (lecturasAnterioresACandidato > k)
			cotaSup = lecturaCandidato - 1;
		
		if (lecturasHastaCandidato <= k)
			cotaInf = lecturaCandidato + 1;
	
    	lecturaCandidato = (cotaSup + cotaInf) / 2;
    	tiempoLecturaCandidato = (lecturaCandidato * minFrecuencia);
    	
    	lecturasAnterioresACandidato = 
    		LecturasHasta(tiempoLecturaCandidato - minFrecuencia, frecuencias);
    	lecturasHastaCandidato = 
    		LecturasHasta(tiempoLecturaCandidato, frecuencias);
    }

	#ifdef custom_dbg
	cout << "LecturaCandidato: " << lecturaCandidato << endl;
	#endif
	

	cotaSupIntervalo = lecturaCandidato * minFrecuencia;
	cotaInfIntervalo = (lecturaCandidato - 1) * minFrecuencia;
	
	vector<int> sensoresCandidato(0);
	
	for (int i = 0; i < n; i++)
		if (LeyoEnIntervalo(frecuencias[i], cotaInfIntervalo, cotaSupIntervalo))
			sensoresCandidato.push_back(i);

	#ifdef custom_dbg			
	cout << "SensoresCandidato: ";
	
	for (int i = 0; i < sensoresCandidato.size(); i ++)
		cout << sensoresCandidato[i] << ", ";
		
	cout << endl;
	#endif
	
	std::sort(sensoresCandidato.begin(), sensoresCandidato.end(), LeyoAntes);

	#ifdef custom_dbg	
	cout << "Candidatos Ordenados: ";
	
	for (int i = 0; i < sensoresCandidato.size(); i ++)
		cout << sensoresCandidato[i] << ", ";
		
	cout << endl;
	#endif
	
	int result = sensoresCandidato[k - LecturasHasta(tiempoLecturaCandidato - 2 * minFrecuencia, frecuencias) - 1] + 1;

	#ifdef custom_dbg	
	cout << "Resultado: " << result << " (frecuencia = " << frecuencias[result -1] << ")" << endl;
	#endif
	
	return result;
}
void salida(ostream& out, int sol){
	out << sol << endl;
}
